#include <bits/stdc++.h>
using namespace std;
typedef pair<double, double> pdd;
const int N = 20, M = 1 << N;
const double eps = 1e-8;
int n, m;
pdd pig[N];
int path[N][N];  // 经过第i、j只猪的抛物线经过了哪些猪
int f[M];

int cmp_lf(double a, double b) {
  if (abs(a - b) < eps) return 0;
  if (a > b)
    return 1;
  else
    return -1;
}

void init_path() {
  memset(path, 0, sizeof path);
  for (int i = 0; i < n; ++i) {
    path[i][i] = 1 << i;  // 一条只经过(0, 0)和第i只猪的抛物线
    auto [x1, y1] = pig[i];
    for (int j = 0; j < n; ++j) {
      auto [x2, y2] = pig[j];
      if (!cmp_lf(x1, x2)) continue;  // x 坐标相同，不可能

      double a = (y1 / x1 - y2 / x2) / (x1 - x2);
      double b = (y1 / x1) - a * x1;
      if (cmp_lf(a, 0.) >= 0) continue;  // 开口向下，a < 0

      // 枚举 y=ax^2+bx 经过的所有猪
      for (int k = 0; k < n; ++k) {
        auto [x, y] = pig[k];
        if (!cmp_lf(y, a * x * x + b * x)) path[i][j] |= 1 << k;
      }
    }
  }
}

void solve() {
  cin >> n >> m;  // m 没有被用到，小孩子才骗分
  for (int i = 0; i < n; ++i) {
    auto& [x, y] = pig[i];
    cin >> x >> y;
  }
  init_path();
  // DP
  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  for (int cur_st = 0; cur_st + 1 < 1 << n; ++cur_st) {
    int t = -1;
    for (int i = 0; i < n; ++i)
      if (!(cur_st >> i & 1)) {
        t = i;  // 第t只猪没被该抛物线击中
        break;  // 加与不加break都正确
      }
    for (int i = 0; i < n; ++i) {
      int ne_st = path[t][i] | cur_st;  // 枚举下一状态
      f[ne_st] = min(f[ne_st], f[cur_st] + 1);
    }
  }
  cout << f[(1 << n) - 1] << endl;  // 完全覆盖
}
int main() {
  int tc = 1;
  cin >> tc;
  while (tc--) solve();
  return 0;
}
